#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

 struct ListNode {
      int val;
      struct ListNode *next;
  };

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL&&list2==NULL)
        return NULL;
    if(list1==NULL&&list2!=NULL)
        return list2;
    if(list2==NULL&&list1!=NULL)
        return list1;
    
    struct ListNode* head = NULL;
    struct ListNode* back = NULL;

    back = head = (struct ListNode*)malloc(sizeof(struct ListNode));
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            back->next = list1;
            list1=list1->next;
        }
        else
        {
            back->next = list2;
            list2 = list2->next;
        }
        back=back->next;
    }
    if(list2!=NULL)
        back->next = list2;
    if(list1!=NULL)
        back->next = list1;
    
    struct ListNode* newnode = head->next;
    free(head);
    return newnode;
}